package class04_归并排序.test;

/**
 * 归并排序
 */
public class Code01_MergeSort {
    public static void mergeSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr,0,arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if(L == R){
            return;
        }
       int M =  L + ((R - L) >> 1);
        process(arr,L,M);
        process(arr,M + 1,R);
        merge(arr,L,M,R);
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int L = l;
        int R = m + 1;
        int h = 0;
        while (L <= m && R <= r){
            help[h++] = arr[L] <= arr[R] ?  arr[L++] : arr[R++];
        }
        while (L <= m){
            help[h++] = arr[L++];
        }
        while (R <= r){
            help[h++] = arr[R++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    //非递归方式实现
    public static void mergeSort2(int[] arr){

        int N = arr.length;
        int mergeSize = 1;
        while (mergeSize < N){
            // 当前左组的，第一个位置
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            // 防止溢出
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }

    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,2,4,5,66,22,33,22};
        mergeSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
